A two-dimensional image, which may for example be an individual image or may be a frame of a video sequence, can conveniently be represented in a computer system as a two-dimensional array of numbers where the numbers encode the brightness of a particular pixel to be displayed on a CRT or other display device. For data compression purposes it is often convenient to represent the array of image data in a more coarsely quantized form. After compression the data is stored in less memory space, but this occurs at the cost of a loss of accuracy. Vector quantization is a well-known enhancement which can be applied to image compression so as to obtain significant reductions in the number of bits required to represent a given image in a computer system.
In vector quantization of a two-dimensional image a codebook of reference patches (e.g. relatively small portions of an image taken from one or more “library” images) is constructed. An image to be compressed is partitioned into a number of image patches and a matching (i.e. similar) reference patch is selected for each patch of the original image, from the codebook. The codebook index for each chosen reference patch in the codebook is stored, together with addressing information (giving the positions of the image patches in the original image) to provide a compressed representation of the image. The chosen codebook index for a patch is often referred to as the “compressed encoding” of the patch. Providing that a copy of the codebook is available, an approximation of the original image can be constructed by using the stored codebook indices to recover the required set of reference patches and inserting these into an image frame using the respective stored image patch position vectors.
WO97/16026 describes an improved vector quantization technique which increases the compression ratio which can be achieved in the compressed image. This technique effectively decides what subdivision will be carried out for individual patches of the original image, when selecting matching reference patches i.e. the size and position of the reference patches from the codebook which will be used to replicate a given patch of the original image. This involves selecting from a plurality of compressed encodings that one of the compressed encodings which, when uncompressed and added to a reference data array, gives the biggest improvement therein relative to the original image data array. The method progressively adds to the reference data array the compressed encodings providing the greatest improvements to the reference array, until a predetermined maximum number of bits are present in the compressed representation, or a desired quality level is achieved in the reference image data array.
One disadvantage of the technique described in WO97/16026 is that there can be interaction between the improvements or “gains” of different patches at different scales, with the result that the image compressor has to repeatedly re-evaluate the gains to be had from different patches. A combinatorial explosion of calculation times would be required to try to calculate the best possible combinations of patches, and this is not practical to implement in the compression apparatus. The technique can therefore result in non-optimal selections of patches. Moreover, the compressed image often has a “blocky” appearance due to discontinuities at the edges of adjacent patches.
It is an object of the present invention to avoid or minimise one of more of the foregoing disadvantages.